package com.ttx.algorithm.leetcode.linkedlist;

/**
 *
 * https://leetcode.com/problems/reverse-linked-list-ii/
 *
 * 反转单链表2
 *
 * @author TimFruit
 * @date 19-1-3 上午12:41
 */
public class P92ReverseLinkedList2 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        //1 <= m <=n <= len of list

        ListNode tempNode=new ListNode(-99999999);
        ListNode reverseStartPointer=head;  // 当前指针， 用于标识反转
        ListNode prev=tempNode; //reverseStartPointer的前一个指针
        prev.next=head;

        int i=1;
        while(i<m){
            i++;
            reverseStartPointer=reverseStartPointer.next;
            prev=prev.next;
        }


        ListNode reverseEndPointer=head; //反转结束的指针, 包括不包括反转该节点
        i=1;
        while(i< (n+1) ){
            i++;
            reverseEndPointer=reverseEndPointer.next;
        }



        ListNode p2=reverseStartPointer;
        ListNode p3=reverseEndPointer;


        ListNode px=null;
        while(p2!=reverseEndPointer){
            px=p2;
            p2=p2.next;

            px.next=p3;
            p3=px;
        }


        prev.next=p3;

        if(prev==tempNode){
            head=prev.next;
        }
        tempNode.next=null;

        return head;

    }

}


